Search for: All records

Abstract Themean subtree orderof a given graph , denoted , is the average number of vertices in a subtree of . Let be a connected graph. Chin et al. conjectured that if is a proper spanning supergraph of , then . Cameron and Mol disproved this conjecture by showing that there are infinitely many pairs of graphs and with , and such that . They also conjectured that for every positive integer , there exists a pair of graphs and with , , and such that . Furthermore, they proposed that provided . In this note, we confirm these two conjectures. 

Abstract Alinear forestis a disjoint union of path graphs. Thelinear arboricity of a graph, denoted by , is the least number of linear forests into which the graph can be partitioned. Clearly, for any graph of maximum degree . For the upper bound, the long‐standingLinear Arboricity Conjecture(LAC) due to Akiyama, Exoo, and Harary from 1981 asserts that . A graph is apseudoforestif each of its components contains at most one cycle. In this paper, we prove thatthe union of any two pseudoforests of maximum degree up to 3 can be decomposed into three linear forests. Combining it with a recent result of Wdowinski on the minimum number of pseudoforests into which a graph can be decomposed, we prove that the LAC holds for the following simple graph classes: ‐degenerate graphs with maximum degree , all graphs on nonnegative Euler characteristic surfaces provided the maximum degree , and graphs on negative Euler characteristic surfaces provided the maximum degree , as well as graphs with no ‐minor satisfying some conditions on maximum degrees.